#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n), dp(n);
        for (int i = 0; i < n; i++)cin >> a[i];
        //dp向量是用来记录以a[i]为结尾的最大子序列和的值
        dp[0] = a[0];
        for (int i = 1; i < n; i++) {
            dp[i] = max(a[i], dp[i - 1] + a[i]);
        }
        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
    return 0;
}

/**
 * 这段代码是用来求解最大子序列和的问题。其中，输入n表示序列的长度，接着读入n个整数，
 * 存储到向量a中。dp向量是用来记录以a[i]为结尾的最大子序列和的值。dp[0]初始化为a[0]，
 * 然后从i=1开始循环，计算dp[i]的值，即为当前元素a[i]和前一个元素结尾的最大子序列和dp[i-1]+a[i]中的较大值。
 * 最后，通过调用max_element函数找到dp中的最大值，输出即为整个序列的最大子序列和。@brief 
 * 
 */